#!/usr/bin/env python
# -*- coding: utf-8 -*-

from typing import List

def solveNQueens(n: int) -> List[List[str]]:
    def generateBoard():
        board = []
        for i in range(len(queens)):
            line = [ '.' ] * n
            line[queens[i]] = 'Q'
            board.append(''.join(line))
        res.append(board)

    def isValid(_c, _r):
        for r in range(n):
            if _c == queens[r]:
                return False
            if abs(queens[r] - _c) == _r - r:
                return False
        return True

    def traceback(_n: int):
        # end condition
        if _n == n:
            generateBoard()
            return
        for i in range(n):
            if not isValid(i, _n):
                continue
            # do selection
            queens[_n] = i
            # next decision
            traceback( _n + 1 )
            # cancel selection
            queens[_n] = -1

    # record 'Q' position in each line
    queens = [ -1 for i in range(n) ]
    res = []
    traceback(0)
    return res;

